1. Field of the Invention
The present invention relates to an error correcting apparatus and, more particularly, to method and apparatus for correcting errors in data to which an error correction code was added.
2. Related Background Art
Hitherto, a product code has been known as a form of an error correction code having a two-dimensional arrangement. FIG. 3 is an arrangement diagram of a product code. In the diagram, the portion of k.sub.1 .times.k.sub.2 corresponds to the original digital information having a two-dimensional arrangement. A predetermined check code m.sub.1 is added to every row in a k.sub.1 direction shown by an arrow A and a code c.sub.l is constructed. On the other hand, a predetermined check code m.sub.2 is added to every column in a k.sub.2 direction shown by an arrow B and a code c.sub.2 is constructed. The code c.sub.1 is the (n.sub.1, k.sub.1) code and the code c.sub.2 is the (n.sub.2, k.sub.2) code.
A sole decoding method in the lateral or vertical direction will be first described as a decoding method of such a code. The error correction decoding method generally includes the following four steps.
step (1) Syndrome calculation PA0 step (2) Calculation of the error position polynomial and error evaluation polynomial PA0 step (3) Estimation of the error position and error value (size) in accordance with the results of the calculation in step 2 PA0 step (4) Execution of the error correction of the estimated position and size
In step (1), since syndromes are obtained as values of the polynomial of the (n-1) order in which all of the symbols of the number corresponding to a code length n of the code are used as coefficients, the arithmetic operation to sequentially input all of the symbols is executed. Therefore, n/S clocks are necessary when the calculation is executed S times in parallel for at least one syndrome. On the other hand, in many cases, S is generally set to 1 to reduce the circuit scale. In this case, the period of time corresponding to n clocks is necessary. With respect to steps (2) to (4) as well, in many cases, the processes are generally executed within the period of time of n clocks.
On the other hand, in the case of the product code construction, a series of error corrections are once executed with respect to the code words of, for instance, n.sub.2 (=k.sub.2 +m.sub.2) rows in the A direction and a series of error corrections.are once performed with regard to the code words of k.sub.1 columns in the B direction. Due to this, the error correcting capability can be raised as compared with the case of, for instance, the construction in only the A direction.
Further, there has been known a repetitive decoding method whereby the error corrections in both of the A and B directions as mentioned above are further repetitively executed to the codes of the product code construction. According to such a method, the error correcting capability can be further raised as compared with the case where the error corrections in the A and B directions are executed once at a time as mentioned above.
However, in the conventional repetitive method, the above steps (1) to (4) are repeated with respect to each of the code words (there are n.sub.2 code words having the arrangement in the A direction and there are n.sub.1 code words having the arrangement in the B direction).
Therefore, assuming that the processes are repetitively executed t times for the period of time of n clocks in step (1) and for the period of time of n clocks in steps (2) to (4), the following processing time is needed. EQU {(n.sub.1 +n.sub.1)n.sub.2 +(n.sub.2 +n.sub.2)k.sub.1 }.times.t=2t(n.sub.1 n.sub.2 +n.sub.2 k.sub.1) (1)
As mentioned above, an extremely long processing time is necessary in the case of executing the repetitive method as mentioned above in order to raise the error correcting capability in the conventional manner.
On the other hand, in any of the A and B directions shown in FIG. 3, in the case of calculating the syndromes, in addition to the problem in the above repetitive method, there is also a problem such that the data shown in FIG. 3 needs to be read out a plurality of times and it is difficult to realize the high speed error correcting operation.
The above problems will now be described with reference to FIGS. 4 and 5.
FIG. 4 is a diagram showing an example of a conventional error detection correction decoding unit.
In FIG. 4, an explanation will be made with respect to the example of the (n-k-2) correction decoding of the data which was double encoded by the code lengths (n.sub.1, k.sub.1) and (n.sub.2, k.sub.2) in the C.sub.1 (lateral) and C.sub.2 (vertical) directions as shown in FIG. 5. The data block including the error correction code (ECC) shown in FIG. 5 is hereinafter referred to as an ECC block.
In the construction shown in FIG. 5, the data to which errors were mixed by the transmission path is first written into a data memory 301 comprising a RAM on a unit basis of n.sub.1 .times.n.sub.2 blocks After that, the data is sequentially read out in the C.sub.1 direction by the address operation of the memory 301 and syndromes are calculated by a syndrome calculating unit 302. The error position and size are calculated by an error detection correction processing unit 303 on the basis of the syndromes calculated, thereby correcting the erroneous data in the data memory 301. After such processes were executed with respect to n.sub.1 lines, the similar processes are also executed in the C.sub.2 direction with regard to n.sub.2 lines. After completion of a series of processes, the error corrected data is read out of the data memory 301 on an ECC block unit basis.
In the conventional example, in order to detect and correct the errors in the ECC block shown in FIG. 4, the following number of access times of the data memory 301 is needed. That is, (n.sub.1 .times.n.sub.2) times are necessary to write the input data. (n.sub.1 .times.n.sub.2) times are necessary to read out to calculate the syndromes in the C.sub.1 direction and (n.sub.1 -k.sub.1 -2) times are necessary per maximum lines to write to correct the data. In the C.sub.2 direction as well, (n.sub.1 .times.n.sub.2) times are similarly necessary to calculate the syndromes, (n.sub.2 -k.sub.2 -2) times per maximum lines are necessary to correct the data, and n.sub.1 .times.n.sub.2) times are necessary to read out the output data. Thus, it is necessary to execute the accessing operations of total 4(n.sub.1 .times.n.sub.2)+.alpha. (.alpha. denotes the number of data to be corrected) times.
As mentioned above, according to the conventional construction, the number of access times of the memory is large. On the other hand, in.realization of the high operating speed (cycle time) of the memory, since it is limited, the processing time of the error detection correction unit is long. In the case where the high operating speed is required, it is necessary to construct the circuits in parallel and to suppress the correcting capability or the like. Such a method causes the correcting capability to deteriorate and increases the circuit scale and a large problem occurs. Further, although the above conventional example has been described with respect to the case of processing the data to which the double encoded error correction code was added, in the case of executing the processes corresponding to the double encoding or more, the number of access times of the memory increases in proportion to them. Therefore, it is necessary to further increase the hardware scale of the processing unit.